class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None


class Solution:
  # 迭代实现二叉树前序、中序、后序遍历
  def frontOrder(self, root: TreeNode) -> list:
    if not root:
      return None
    res, stack = list(), [root]
    while len(stack) > 0:
      node = stack.pop()
      res.append(node.val)
      if node.right:
        stack.append(node.right)
      if node.left:
        stack.append(node.left)
    return res
  
  def midOrder(self, root: TreeNode) -> list:
    if not root:
      return None
    res, stack = list(), list()
    while len(stack) > 0 or root:
      while root:
        stack.append(root)
        root = root.left
      if len(stack) > 0:
        node = stack.pop()
        res.append(node.val)
        root = node.right
    return res
  
  def postOrder(self, root: TreeNode) -> list:
    if not root:
      return None
    res, stack = list(), [root]
    while len(stack) > 0:
      node = stack.pop()
      if node.left:
        stack.append(node.left)
      if node.right:
        stack.append(node.right)
      res.insert(0, node.val)
    return res
    

if __name__ == "__main__":
  solution = Solution()
  # 定义一个测试二叉树
  root = TreeNode(1)
  root.left = TreeNode(2)
  root.right = TreeNode(3)
  root.left.left = TreeNode(6)
  root.right.left = TreeNode(4)
  root.right.right = TreeNode(5)
  print(solution.frontOrder(root))
  print(solution.midOrder(root))
  print(solution.postOrder(root))
